/**
 * 插入排序：
 * 1、申请一个新的数组
 * 2、以第一个数为基准值，依次遍历1~n，取出的值R同结果数组[result]进行对比，因结果数组是有序的，故可以将R插入[result]中，一次遍历即可
 * 3、可以申请一个新空间，也可以在原数组上直接操作数组元素
 * @param {Array} array 
 */
var insertSort = function (array) {
  let base = array[0];
  let result = [base];
  for (let i = 1; i < array.length; i++) {
    let item = array[i];

    let min = result[0];
    let max = result[result.length - 1];
    if (min < item && item < max) {
      for (let j = 0; j < result.length; j++) {
        let rj = result[j];
        if (rj > item) {
          result.splice(j, 1, item, rj);
          break;
        }
      }
    } else {
      if (item <= min) {
        result.unshift(item);
      } else if (item >= max) {
        result.push(item);
      }
    }
  }
  return result;
}

// 原数组上处理元素
var insertSort2 = function (array) {
  let j;
  for (let i = 1; i < array.length; i++) {
    let item = array[i];
    for (j = i - 1; j >= 0 && array[j] > item; j--) {
      array[j+1] = array[j];
    }
    // 补回原来数字
    array[j + 1] = item;
    // for (let j = 0; j < i; j++) {
    //   let rj = array[j];
    //   // 插入到数组指定位置
    //   if (item < rj) {
    //     // 删除第i个元素
    //     array.splice(i, 1);
    //     // 在指定位置插入元素
    //     array.splice(j, 1, item, rj);
    //     break;
    //   }
    // }
  }
  return array;
}

console.log(insertSort2([69, 65, 90, 6, 22, 6, 65, 70]))